package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/count-ways-to-build-good-strings/description/
 *
 * 2466.统计好字符串的数目
 *
 * 给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：
 *
 * 将 '0' 在字符串末尾添加 zero  次。
 * 将 '1' 在字符串末尾添加 one 次。
 * 以上操作可以执行任意次。
 *
 * 如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。
 *
 * 请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余 后返回。
 *
 *
 *
 * 示例 1：
 *
 * 输入：low = 3, high = 3, zero = 1, one = 1
 * 输出：8
 * 解释：
 * 一个可能的好字符串是 "011" 。
 * 可以这样构造得到："" -> "0" -> "01" -> "011" 。
 * 从 "000" 到 "111" 之间所有的二进制字符串都是好字符串。
 * 示例 2：
 *
 * 输入：low = 2, high = 3, zero = 1, one = 2
 * 输出：5
 * 解释：好字符串为 "00" ，"11" ，"000" ，"110" 和 "011" 。
 *
 * @author hanjuntao
 * @date 2025/7/25 0025
 */
public class L_2466_count_ways_to_build_good_strings {

    public static void main(String[] args) {
        System.out.println(countGoodStrings(3, 3, 1, 1)); // 8
        System.out.println(countGoodStrings(2, 3, 1, 2)); // 5
    }

    /**
     * 思路：
     *
     * 从题意可以，每次添加字符，可以选择添加0或者1，每次添加的字段的个数由zero和one决定
     *
     * 这个属于组合问题，可以映射为爬楼梯问题，每次爬zero，或者one个台阶, 楼梯数量为high
     *
     *
     *  状态转移方程：
     *
     *  dp[i] = 【i >= zero:】dp[i-zero] + 【i >= one:】 dp[i-one]
     *
     *  需要判断 i >= zero 和 i >= one 才可以执行状态转移方程
     *
     * 结果：
     * 从状态转移方程，遍历low 到 high的结果累加起来，即为结果
     *
     *
     * @param low
     * @param high
     * @param zero
     * @param one
     * @return
     */
    public static int countGoodStrings(int low, int high, int zero, int one) {
        long m = 1000000007;

        long [] dp = new long[high + 1];
        dp[0] = 1;

        for (int i = 1; i <= high; i++) {
            long temp = 0;
            if (i >= zero) {
                temp += (dp[i - zero]) % m;
            }
            if (i >= one) {
                temp += (dp[i - one]) % m;
            }

            dp[i] = (temp % m);
        }

        long sum = 0;
        for (int i = low; i <= high; i++) {
            sum += (dp[i]) % m;
        }

        return (int) (sum % m);
    }
}
